package com.leetcode.根据算法进行分类.单调栈相关;

import java.util.*;

/**
 * @author: ZhouBert
 * @date: 2021/2/8
 * @description: 84. 柱状图中最大的矩形
 * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 */
public class C_84_柱状图中最大的矩形 {

	public static void main(String[] args) {
		C_84_柱状图中最大的矩形 action = new C_84_柱状图中最大的矩形();
		test1(action);
		test2(action);
	}

	public static void test1(C_84_柱状图中最大的矩形 action) {
		//10
		int[] heights = new int[]{2, 1, 5, 6, 2, 3};
		int res = action.largestRectangleAreaByStack(heights);
		System.out.println("res = " + res);
	}

	public static void test2(C_84_柱状图中最大的矩形 action) {
		//4
		int[] heights = new int[]{2, 4};
		int res = action.largestRectangleAreaByStack(heights);
		System.out.println("res = " + res);
	}

	/**
	 * 来学习一下利用单调栈来解决问题
	 * 调试了下，发现：确实可以用单调栈来解决问题。
	 * 但是单调栈太抽象了，感觉不到使用的契机。
	 * --
	 * 首先理一下思路：
	 * 针对 {2, 1, 5, 6, 2, 3} 的例子
	 * 1.遍历到2 时，无法确定该位置的 area【指的是：以此高度的矩形的面积】,因为虽然 left 已经确定，但是 right 木有确定；于是继续遍历；
	 * 2.遍历到1 时，（此时 1 < 2）发现 2 的 area 已经可以确定，于是 2 的数据可以舍弃；
	 * 3.遍历到5 时，由于 5 > 1，此时 1 的 area 还不能确定，需要保留（于是入栈，发现入栈的意义就是保留）
	 * 4.遍历到6 时，由于 6 > 5，此时 5 的 area 还不能确定，需要保留，入栈；
	 * 5.遍历到2 时，发现了 6 > 2，此时就可以确定高度为 6 的面积，先将 6 的索引出栈，
	 * area = 此时的索引 - 栈顶元素的索引 - 1
	 * 以此类推...
	 * 太不容易了，得仔细体会体会！
	 * [6 比 5 晚遍历到，但是先算出结果！符合 LIFO 的规律！由此可以联想到 stack !!!]
	 * @param heights
	 * @return
	 */
	private int largestRectangleAreaByStack(int[] heights) {
		//1.初始状态确定
		int len = heights.length;
		if (len == 0) {
			return 0;
		}
		if (len == 1) {
			return heights[0];
		}
		//2.
		int res = 0;
		ArrayDeque<Integer> stack = new ArrayDeque<>();
		for (int i = 0; i < len; i++) {
			while (!stack.isEmpty() && heights[stack.peekLast()] > heights[i]) {
				//当 下一个元素小于栈顶元素时 -> 出栈
				int height = heights[stack.removeLast()];

				while (!stack.isEmpty() && heights[stack.peekLast()] == height) {
					stack.removeLast();
				}

				int width;
				if (stack.isEmpty()) {
					width = i;
				} else {
					width = i - stack.peekLast() - 1;
				}
				//此时计算出来的是 从栈弹出的元素所能生成的最大面积
				//
				res = Math.max(res, width * height);
			}
			stack.addLast(i);
		}

		while (!stack.isEmpty()){
			int height = heights[stack.removeLast()];
			while (!stack.isEmpty() && heights[stack.peekLast()]==height){
				stack.removeLast();
			}

			int width;
			if (stack.isEmpty()){
				width=len;
			}else {
				width=len-stack.peekLast()-1;
			}
			res = Math.max(res, width * height);
		}
		return res;
	}

	/**
	 * 通过 哨兵（优化）和 单调栈
	 * 但是需要多遍历一遍，用于将 0 的值填入 左右边界。
	 * @param heights
	 * @return
	 */
	private int largestRectangleAreaByStackAndGuard(int[] heights){
		int len = heights.length;
		if (len == 0) {
			return 0;
		}
		if (len == 1) {
			return heights[0];
		}

		int area = 0;
		int[] newHeights = new int[len + 2];
		for (int i = 0; i < len; i++) {
			newHeights[i + 1] = heights[i];
		}
		len += 2;
		heights = newHeights;

		Deque<Integer> stack = new ArrayDeque<>();
		stack.addLast(0);

		for (int i = 1; i < len; i++) {
			while (heights[stack.peekLast()] > heights[i]) {
				int height = heights[stack.removeLast()];
				int width  = i - stack.peekLast() - 1;
				area = Math.max(area, width * height);
			}
			stack.addLast(i);
		}
		return area;
	}



	/**
	 * 这道题看起来似乎应该用 单调栈 来解决；但是我想不到，于是我还是用 heap 来吧
	 * 最差的情况：[1,1,1,....] 跟暴力解法差不多。最终会超出时间限制！
	 * --
	 * 用 heap 的方法太深入业务了，需要讨论的情况太复杂了！
	 *
	 * @param heights
	 * @return
	 */
	public int largestRectangleAreaByHeap(int[] heights) {
		//1.初始状态确定
		int len = heights.length;
		int res = 0;
		if (len == 0) {
			return res;
		}
		if (len == 1) {
			return heights[0];
		}
		//2.将 元素添加入堆
		PriorityQueue<Peak> heap = new PriorityQueue<>(new Comparator<Peak>() {
			@Override
			public int compare(Peak o1, Peak o2) {
				return o1.value - o2.value;
			}
		});
		for (int i = 0; i < len; i++) {
			heap.offer(new Peak(i, heights[i]));
		}
		//3.使用 hashSet 用来存放上一个值的集合
		HashSet<Integer> set = new HashSet<>();
		int lastValue = 0;
		//记录 是否已经执行过位置的索引
		int[] recordArr = new int[len];
		Peak curPeak;
		int left = 0, right = len - 1;
		int width = 0;
		while (!heap.isEmpty()) {
			curPeak = heap.poll();
			// 1 表示 待定
			recordArr[curPeak.index] = 1;
			if (set.isEmpty()) {
				//说明是第一个，可以无限延伸
				res = heights[curPeak.index] * len;
			} else {
				//说明不是第一个，开始从当前位置往左右两边延伸
				left = curPeak.index;
				right = curPeak.index;
				if (lastValue == curPeak.value) {
					//如果上一个值跟当前值相等-> 这就比较复杂
					while (left > 0) {
						if (recordArr[left - 1] == 0 || set.contains(left - 1)) {
							left--;
						} else {
							break;
						}
					}
					while (right < len - 1) {
						if (recordArr[right + 1] == 0 || set.contains(right + 1)) {
							right++;
						} else {
							break;
						}
					}
				} else {
					set.clear();
					//如果上个值跟当前值不相等
					//只要往左右延伸知道 recordArr[i] == 1
					while (left > 0) {
						if (recordArr[left - 1] == 0) {
							left--;
						} else {
							break;
						}
					}
					while (right < len - 1) {
						if (recordArr[right + 1] == 0) {
							right++;
						} else {
							break;
						}
					}
				}
				width = right - left + 1;
				res = Math.max(heights[curPeak.index] * width, res);
			}
			lastValue = curPeak.value;
			set.add(curPeak.index);
		}
		return res;

	}

	static class Peak {
		int index;
		int value;

		public Peak(int index, int value) {
			this.index = index;
			this.value = value;
		}
	}
}
